package chapter04;

import java.nio.BufferUnderflowException;

public class BinarySearchTree<E  extends Comparable<? super E>>{

    private BinaryNode<E> root;

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(BinaryNode<E> root) {
        this.root = root;
    }

    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    /**
     * @param e
     * @return
     */
    public boolean contains(E e) {
        return contains(e, root);
    }

    public E findMin() {
        if (isEmpty()) {
            throw new BufferUnderflowException();
        }
        E element = findMin(root).element;
        return element;
    }

    public E findMax() {
        if (isEmpty()) {
            throw new BufferUnderflowException();
        }
        E element = findMax(root).element;
        return element;
    }

    public void insert(E e) {
        root = insert(e, root);
    }

    public void remove(E e) {
        root = remove(e, root);
    }

    public void printTree() {
        printTree(root);
        System.out.println();
    }

    /**
     * Internal method to find an item in a subtree.
     * @param e is item to search for.
     * @param node the node that roots the subtree.
     * @return node containing the matched item.
     */
    private boolean contains(E e, BinaryNode<E> node) {
        if (node == null) {
            return false;
        }
        int compareResult = e.compareTo(node.element);

        if (compareResult < 0) {
            return contains(e, node.left);
        }else if (compareResult > 0) {
            return contains(e, node.right);
        }else {
            return true;
        }
    }

    private BinaryNode<E> findMin(BinaryNode<E> node) {
        if (node == null) {
            return null;
        }else if (node.left == null) {
            return node;
        }else {
            return findMin(node.left);
        }
    }

    private BinaryNode<E> findMax(BinaryNode<E> node) {
        if (node == null) {
            return null;
        }else if (node.right == null) {
            return node;
        }else {
            return findMax(node.right);
        }
    }

    private BinaryNode<E> insert(E e, BinaryNode<E> node) {
        if (node == null) {
            return new BinaryNode<>(e);
        }
        int compareResult = e.compareTo(node.element);

        if (compareResult < 0) {
            node.left = insert(e, node.left);
        }else if (compareResult > 0) {
            node.right = insert(e, node.right);
        }else {

        }
        return node;
    }

    private BinaryNode<E> remove(E e, BinaryNode<E> node) {
        if (node == null) {
            return node;    // Item not found; do nothing
        }
        int compareResult = e.compareTo(node.element);

        if (compareResult < 0) {
            node.left = remove(e, node.left);
        } else if (compareResult > 0) {
            node.right = remove(e, node.right);
        } else {
            if (node.left != null && node.right != null) {      //两个节点
                node.element = findMin(node.right).element;
                node.right = remove(node.element, node.right);
            } else if (node.left != null) {     //一个节点
                node = node.left;
            } else if (node.right != null) {     //一个节点
                node = node.right;
            } else {    //零个节点
                node = null;
            }
        }
        return node;
    }

    private void printTree(BinaryNode<E> node) {
        if (node == null) {
            return;
        }
        printTree(node.left);
        System.out.println(node.element);
        printTree(node.right);
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> tree = new BinarySearchTree<>();
        tree.insert(10);
        tree.insert(8);
        tree.insert(11);
        //tree.printTree();

        tree.insert(9);
        //tree.printTree();

        tree.remove(8);
        tree.printTree();

        Integer min = tree.findMin();
        System.out.println(min);

        Integer max = tree.findMax();
        System.out.println(max);

        boolean contains = tree.contains(91);
        System.out.println(contains);

    }
}
